{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Exclusive Time of Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: exclusiveTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #函数的独占时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个 <strong>单线程</strong> CPU 正在运行一个含有 <code>n</code> 道函数的程序。每道函数都有一个位于  <code>0</code> 和 <code>n-1</code> 之间的唯一标识符。</p>\n",
    "\n",
    "<p>函数调用 <strong>存储在一个 <a href=\"https://baike.baidu.com/item/%E8%B0%83%E7%94%A8%E6%A0%88/22718047?fr=aladdin\" target=\"_blank\">调用栈</a> 上</strong> ：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是 <strong>当前正在执行的函数</strong> 。每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。</p>\n",
    "\n",
    "<p>给你一个由日志组成的列表 <code>logs</code> ，其中 <code>logs[i]</code> 表示第 <code>i</code> 条日志消息，该消息是一个按 <code>\"{function_id}:{\"start\" | \"end\"}:{timestamp}\"</code> 进行格式化的字符串。例如，<code>\"0:start:3\"</code> 意味着标识符为 <code>0</code> 的函数调用在时间戳 <code>3</code> 的 <strong>起始开始执行</strong> ；而 <code>\"1:end:2\"</code> 意味着标识符为 <code>1</code> 的函数调用在时间戳 <code>2</code> 的 <strong>末尾结束执行</strong>。注意，函数可以 <strong>调用多次，可能存在递归调用 </strong>。</p>\n",
    "\n",
    "<p>函数的 <strong>独占时间</strong> 定义是在这个函数在程序所有函数调用中执行时间的总和，调用其他函数花费的时间不算该函数的独占时间。例如，如果一个函数被调用两次，一次调用执行 <code>2</code> 单位时间，另一次调用执行 <code>1</code> 单位时间，那么该函数的 <strong>独占时间</strong> 为 <code>2 + 1 = 3</code> 。</p>\n",
    "\n",
    "<p>以数组形式返回每个函数的 <strong>独占时间</strong> ，其中第 <code>i</code> 个下标对应的值表示标识符 <code>i</code> 的函数的独占时间。</p>\n",
    " \n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/04/05/diag1b.png\" style=\"width: 550px; height: 239px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, logs = [\"0:start:0\",\"1:start:2\",\"1:end:5\",\"0:end:6\"]\n",
    "<strong>输出：</strong>[3,4]\n",
    "<strong>解释：</strong>\n",
    "函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，于时间戳 1 的末尾结束执行。 \n",
    "函数 1 在时间戳 2 的起始开始执行，执行 4 个单位时间，于时间戳 5 的末尾结束执行。 \n",
    "函数 0 在时间戳 6 的开始恢复执行，执行 1 个单位时间。 \n",
    "所以函数 0 总共执行 2 + 1 = 3 个单位时间，函数 1 总共执行 4 个单位时间。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, logs = [\"0:start:0\",\"0:start:2\",\"0:end:5\",\"0:start:6\",\"0:end:6\",\"0:end:7\"]\n",
    "<strong>输出：</strong>[8]\n",
    "<strong>解释：</strong>\n",
    "函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。\n",
    "函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。\n",
    "函数 0（初始调用）恢复执行，并立刻再次调用它自身。\n",
    "函数 0（第二次递归调用）在时间戳 6 的起始开始执行，执行 1 个单位时间。\n",
    "函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间。\n",
    "所以函数 0 总共执行 2 + 4 + 1 + 1 = 8 个单位时间。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, logs = [\"0:start:0\",\"0:start:2\",\"0:end:5\",\"1:start:6\",\"1:end:6\",\"0:end:7\"]\n",
    "<strong>输出：</strong>[7,1]\n",
    "<strong>解释：</strong>\n",
    "函数 0 在时间戳 0 的起始开始执行，执行 2 个单位时间，并递归调用它自身。\n",
    "函数 0（递归调用）在时间戳 2 的起始开始执行，执行 4 个单位时间。\n",
    "函数 0（初始调用）恢复执行，并立刻调用函数 1 。\n",
    "函数 1在时间戳 6 的起始开始执行，执行 1 个单位时间，于时间戳 6 的末尾结束执行。\n",
    "函数 0（初始调用）在时间戳 7 的起始恢复执行，执行 1 个单位时间，于时间戳 7 的末尾结束执行。\n",
    "所以函数 0 总共执行 2 + 4 + 1 = 7 个单位时间，函数 1 总共执行 1 个单位时间。 </pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, logs = [\"0:start:0\",\"0:start:2\",\"0:end:5\",\"1:start:7\",\"1:end:7\",\"0:end:8\"]\n",
    "<strong>输出：</strong>[8,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, logs = [\"0:start:0\",\"0:end:0\"]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 100</code></li>\n",
    "\t<li><code>1 <= logs.length <= 500</code></li>\n",
    "\t<li><code>0 <= function_id < n</code></li>\n",
    "\t<li><code>0 <= timestamp <= 10<sup>9</sup></code></li>\n",
    "\t<li>两个开始事件不会在同一时间戳发生</li>\n",
    "\t<li>两个结束事件不会在同一时间戳发生</li>\n",
    "\t<li>每道函数都有一个对应 <code>\"start\"</code> 日志的 <code>\"end\"</code> 日志</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [exclusive-time-of-functions](https://leetcode.cn/problems/exclusive-time-of-functions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [exclusive-time-of-functions](https://leetcode.cn/problems/exclusive-time-of-functions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[\"0:start:0\",\"1:start:2\",\"1:end:5\",\"0:end:6\"]', '1\\n[\"0:start:0\",\"0:start:2\",\"0:end:5\",\"0:start:6\",\"0:end:6\",\"0:end:7\"]', '2\\n[\"0:start:0\",\"0:start:2\",\"0:end:5\",\"1:start:6\",\"1:end:6\",\"0:end:7\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "3\n",
    "[\"0:start:0\",\"0:end:0\",\"1:start:1\",\"1:end:1\",\"2:start:2\",\"2:end:2\",\"2:start:3\",\"2:end:3\"]\n",
    "2\n",
    "[\"0:start:0\",\"1:start:2\",\"1:end:5\",\"0:end:6\"]\n",
    "1\n",
    "[\"0:start:0\",\"0:start:2\",\"0:end:5\",\"0:start:6\",\"0:end:6\",\"0:end:7\"]\n",
    "2\n",
    "[\"0:start:0\",\"0:start:2\",\"0:end:5\",\"1:start:6\",\"1:end:6\",\"0:end:7\"]\n",
    "\n",
    "1 <= n <= 100\n",
    "1 <= logs.length <= 500\n",
    "0 <= function_id < n\n",
    "0 <= timestamp <= 10^9\n",
    "No two start events will happen at the same timestamp.\n",
    "No two end events will happen at the same timestamp.\n",
    "Each function has an \"end\" log for each \"start\" log.\n",
    "\n",
    "Stack, Array\n",
    "\"\"\"\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, s):\n",
    "        fn, type, ts = s.split(':')\n",
    "        self.fn = int(fn)\n",
    "        self.type = type\n",
    "        ts = int(ts)\n",
    "        ts += 0 if type == 'start' else 1\n",
    "        self.ts = ts\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        res = [0]*n\n",
    "        node = Node(logs[0])\n",
    "        pre = node.ts\n",
    "        st = [node.fn]\n",
    "        for i in range(1, len(logs)):\n",
    "            node = Node(logs[i])\n",
    "            if st:\n",
    "                res[st[-1]] += node.ts - pre\n",
    "            if node.type == 'start':\n",
    "                st.append(node.fn)\n",
    "            else:\n",
    "                st.pop()\n",
    "            pre = node.ts\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        ans = [0] * n\n",
    "        for log in logs:\n",
    "            (f, call, t) = log.split(\":\")\n",
    "            f, t = int(f), int(t)\n",
    "            if call[0] == \"s\":\n",
    "                if len(stack):\n",
    "                    ans[stack[-1][0]] += \\\n",
    "                            t - stack[-1][1]\n",
    "                stack.append([f, t])\n",
    "            else:\n",
    "                ff, tt = stack.pop() \n",
    "                ans[f] += t - tt + 1\n",
    "                if len(stack):\n",
    "                    stack[-1][1] = t + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        def helper(log):\n",
    "            idx, mark, time = log.split(\":\")\n",
    "            return int(idx), mark == \"start\", int(time)\n",
    "\n",
    "        stack, ans, total = [], [0] * n, 0\n",
    "        for lg in logs:\n",
    "            idx, is_start, time = helper(lg)\n",
    "            if is_start:\n",
    "                stack.append(total - time)\n",
    "            else:\n",
    "                d = stack.pop()\n",
    "                diff = time + 1 + d - total\n",
    "                ans[idx] += diff\n",
    "                total += diff\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "\t\tdef helper(log):\n",
    "\t\t\tidx, mark, time = log.split(\":\")\n",
    "\t\t\treturn int(idx), mark == \"start\", int(time)\n",
    "\n",
    "\t\tst = []\n",
    "\t\tans = [0] * n\n",
    "\t\ttotal = 0\n",
    "\t\tfor log in logs:\n",
    "\t\t\tidx, is_start, time = helper(log)\n",
    "\t\t\tif is_start:\n",
    "\t\t\t\tst.append((total-time))\n",
    "\t\t\telse:\n",
    "\t\t\t\td = st.pop()\n",
    "\t\t\t\tdiff = time + 1 - total + d\n",
    "\t\t\t\tans[idx] += diff\n",
    "\t\t\t\ttotal += diff\n",
    "\t\treturn ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "        prev = 0\n",
    "        for ch in logs:\n",
    "            f_id, flag, time = ch.split(\":\")\n",
    "            f_id, time = int(f_id), int(time)\n",
    "            if flag == \"start\":\n",
    "                if stack:\n",
    "                    res[stack[-1]] += time - prev\n",
    "                stack.append(f_id)\n",
    "                prev = time\n",
    "            else:\n",
    "                res[stack.pop()] += time - prev + 1\n",
    "                prev = time + 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        res = [0] * n\n",
    "        stack = []\n",
    "        prev = 0\n",
    "        for log in logs:\n",
    "            fid, flag, time = log.split(\":\")\n",
    "            fid, time = int(fid), int(time)\n",
    "            if flag == \"start\":\n",
    "                if stack:\n",
    "                    res[stack[-1]] += time - prev\n",
    "                stack.append(fid)\n",
    "                prev = time\n",
    "            else:\n",
    "                res[stack.pop()] += time - prev + 1\n",
    "                prev = time + 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        res = [0] * n\n",
    "        stack = []\n",
    "        for point in logs:\n",
    "            info = point.split(':')\n",
    "            no = int(info[0])\n",
    "            type = info[1]\n",
    "            time = int(info[2])\n",
    "            # 处理折叠的核心：更新start的时间\n",
    "            # start 直接算差值 并更新start点\n",
    "            # end 时候 end+1就为新的start点\n",
    "            if type == 'start':\n",
    "                if stack:\n",
    "                    res[stack[-1][0]] += time - stack[-1][1]\n",
    "                    stack[-1][1] = time\n",
    "                stack.append([no,time])\n",
    "            else:\n",
    "                res[no] +=  time - stack.pop()[1] + 1\n",
    "                if stack:\n",
    "                     stack[-1][1] = time + 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        # logs.sort(key=lambda x: int(x.split(':')[-1]))  # 非必要操作\n",
    "        ans = [0] * n\n",
    "        st = list()\n",
    "        for log in logs:\n",
    "            function_id, tag, timestamp = log.split(':')\n",
    "            function_id, timestamp = map(int, (function_id, timestamp))\n",
    "            if tag == \"start\":\n",
    "                if st:\n",
    "                    cur_id = st[-1]\n",
    "                    ans[cur_id] += timestamp - cur\n",
    "                st.append(function_id)\n",
    "                cur = timestamp\n",
    "            else:\n",
    "                st.pop()\n",
    "                ans[function_id] += timestamp - cur + 1\n",
    "                cur = timestamp + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "        start = 0\n",
    "        for ch in logs:\n",
    "            f_id, flag, time = ch.split(\":\")\n",
    "            f_id, time = int(f_id), int(time)\n",
    "            if flag == \"start\":\n",
    "                if stack:\n",
    "                    res[stack[-1]] += time - start\n",
    "                stack.append(f_id)\n",
    "                start = time\n",
    "            else:\n",
    "                res[stack.pop()] += time - start + 1\n",
    "                start = time + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans=[0]*n\n",
    "        st=[]\n",
    "        for log in logs:\n",
    "            idx,tp,timestep=log.split(\":\")\n",
    "            idx,timestep=int(idx),int(timestep)\n",
    "            if tp[0]=='s':\n",
    "                if st:\n",
    "                    ans[st[-1][0]]+=timestep-st[-1][1]\n",
    "                    st[-1][1]=timestep\n",
    "                st.append([idx,timestep])\n",
    "            else:\n",
    "                i,t=st.pop()\n",
    "                ans[i]+=timestep-t+1\n",
    "                if st:\n",
    "                    st[-1][1]=timestep+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        res = [0] * n\n",
    "        stack = []\n",
    "        for log in logs:\n",
    "            infos = log.split(':')\n",
    "            iid, time = int(infos[0]), int(infos[2])\n",
    "            if infos[1] == 'start':\n",
    "                if len(stack):\n",
    "                    res[stack[-1][0]] += time - stack[-1][1]\n",
    "                stack.append([iid, time])\n",
    "            else:\n",
    "                res[stack[-1][0]] += time + 1 - stack[-1][1]\n",
    "                stack.pop()\n",
    "                if len(stack):\n",
    "                    stack[-1][1] = time + 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        time = [0] * n\n",
    "        function_stk = []\n",
    "        pre_time = []\n",
    "        for l in logs:\n",
    "            f, mode, t = l.split(':')\n",
    "            if mode == 'start':\n",
    "                function_stk.append((f, t))\n",
    "                pre_time.append(0)\n",
    "            else:\n",
    "                cur_time = int(t) - int(function_stk[-1][1]) + 1 - pre_time[-1]\n",
    "                time[int(f)] += cur_time\n",
    "                pre_time[-1] += cur_time\n",
    "                function_stk.pop()\n",
    "                if function_stk:\n",
    "                    p = pre_time.pop()\n",
    "                    pre_time[-1] += p\n",
    "                else:\n",
    "                    pre_time = []\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans= [0]*n\n",
    "        st=[]\n",
    "\n",
    "        for log in logs:\n",
    "            idx,tp,time = log.split(\":\")\n",
    "            idx,time=int(idx),int(time)\n",
    "            if tp == \"start\" :\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += time-st[-1][1]\n",
    "                    st[-1][1]=time\n",
    "                st.append([idx,time])\n",
    "            else:\n",
    "                i,t=st.pop()\n",
    "                ans[i] += time -t +1\n",
    "                if st:\n",
    "                    st[-1][1]=time+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "        cur_time = -1\n",
    "        for log in logs:\n",
    "            # print(cur_time)\n",
    "            ids, opt, time = log.split(':')\n",
    "            if opt == 'start': \n",
    "                if len(stack) == 0:\n",
    "                    stack.append(int(ids))\n",
    "                else:\n",
    "                    res[stack[-1]] += int(time) - 1 - cur_time\n",
    "                    stack.append(int(ids))\n",
    "                    cur_time = int(time) - 1\n",
    "            else:\n",
    "                index = stack.pop()\n",
    "                res[index] += int(time) - cur_time\n",
    "                cur_time = int(time)\n",
    "                \n",
    "\n",
    "        return res\n",
    "                \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef exclusiveTime(self, n, logs):\n",
    "\t\tans = [0] * n\n",
    "\t\ta = []\n",
    "\t\tfor s in logs:\n",
    "\t\t\tp = s.split(':')\n",
    "\t\t\tid, act, t = int(p[0]), p[1], int(p[2])\n",
    "\t\t\tif act == 'start':\n",
    "\t\t\t\tif a: ans[a[-1][0]] += t - a[-1][1]\n",
    "\t\t\t\ta.append([id, t])\n",
    "\t\t\telse:\n",
    "\t\t\t\tans[id] += t - a[-1][1] + 1\n",
    "\t\t\t\ta.pop()\n",
    "\t\t\t\tif a: a[-1][1] = t + 1\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(\":\")\n",
    "            idx,timestamp = int(idx), int(timestamp)\n",
    "            if tp[0] == 's':\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += timestamp - st[-1][1]\n",
    "                    st[-1][1] = timestamp\n",
    "                st.append([idx,timestamp])\n",
    "            else:\n",
    "                i,t = st.pop()\n",
    "                ans[i] += timestamp - t + 1\n",
    "                if st:\n",
    "                    st[-1][1] = timestamp + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        stack = []\n",
    "        for log in logs:\n",
    "            (func, kind, ix) = log.split(':')\n",
    "            func, ix = int(func), int(ix)\n",
    "            if kind == 'start':\n",
    "                stack.append((func, ix))\n",
    "            else:\n",
    "                top = stack.pop()\n",
    "                ans[func] += (ix - top[1] + 1)\n",
    "                if len(stack) > 0:\n",
    "                    ans[stack[-1][0]] -= (ix - top[1] + 1)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        time = [0]*100\n",
    "        max_job_id = -1\n",
    "        last_time = 0\n",
    "        for log in logs:\n",
    "            log = log.split(':')\n",
    "            id = int(log[0])\n",
    "            command = log[1]\n",
    "            cur_time = int(log[2])\n",
    "            if command == 'start':\n",
    "                if stack:\n",
    "                    time[stack[-1]]+=cur_time-last_time\n",
    "                stack.append(id)\n",
    "                max_job_id = max(max_job_id,id)\n",
    "                last_time = cur_time\n",
    "            else:\n",
    "                stack.pop()\n",
    "                time[id]+=cur_time-last_time+1\n",
    "                last_time = cur_time+1\n",
    "        return time[:max_job_id+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        # stack = []\n",
    "        # prev_time = 0 \n",
    "        # cum_time = [0] * n #累计每个funcid的时间\n",
    "\n",
    "\n",
    "        # for log in logs:\n",
    "        #     func_id,call_type, timestamp = log.split(':')\n",
    "        #     func_id = int(func_id)\n",
    "        #     timestamp = int(timestamp)\n",
    "\n",
    "        #     if call_type == 'start':\n",
    "\n",
    "        #         if stack:\n",
    "        #             cum_time[stack[-1]] += timestamp - prev_time\n",
    "\n",
    "        #         stack.append(func_id) #存func id\n",
    "        #         prev_time = timestamp\n",
    "            \n",
    "        #     else:\n",
    "\n",
    "        #         cum_time[stack.pop()] += timestamp - prev_time +1\n",
    "        #         prev_time = timestamp + 1\n",
    "        \n",
    "        # return cum_time\n",
    "\n",
    "\n",
    "        execution_time = [0 ]*n\n",
    "        func_stack = []\n",
    "        prev_time = 0\n",
    "\n",
    "        for log in logs:\n",
    "            func_id, call_type, timestamp = log.split(':')\n",
    "            func_id = int(func_id)\n",
    "            timestamp = int(timestamp)\n",
    "\n",
    "            if call_type == 'start':\n",
    "                if func_stack:\n",
    "                    execution_time[func_stack[-1]] += timestamp - prev_time\n",
    "                \n",
    "                func_stack.append(func_id)\n",
    "                prev_time = timestamp\n",
    "\n",
    "            else: #\n",
    "                execution_time[func_stack.pop()] += timestamp - prev_time +1\n",
    "                prev_time = timestamp +1\n",
    "            \n",
    "        return execution_time\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        def helper(log):\n",
    "            idx, mark, time = log.split(\":\")\n",
    "            return int(idx), mark == \"start\", int(time)\n",
    "\n",
    "        stack, ans, total = [], [0] * n, 0\n",
    "        for lg in logs:\n",
    "            idx, is_start, time = helper(lg)\n",
    "            if is_start:\n",
    "                stack.append((idx, time, total))\n",
    "            else:\n",
    "                _, t, s = stack.pop()\n",
    "                diff = time + 1 - t - total + s\n",
    "                ans[idx] += diff\n",
    "                total += diff\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "\t\tdef helper(log):\n",
    "\t\t\tidx,mark,t = log.split(\":\")\n",
    "\t\t\treturn int(idx),mark == 'start', int(t)\n",
    "\t\tst = []\n",
    "\t\tans = n * [0]\n",
    "\t\ttotal = 0\n",
    "\t\tfor log in logs:\n",
    "\t\t\tidx,is_mart,time = helper(log)\n",
    "\t\t\tif is_mart:\n",
    "\t\t\t\tst.append(total - time)\n",
    "\t\t\telse:\n",
    "\t\t\t\td = st.pop()\n",
    "\t\t\t\tdiff = time + 1 + d - total\n",
    "\t\t\t\tans[idx] += diff\n",
    "\t\t\t\ttotal += diff\n",
    "\t\treturn ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [0]*n\n",
    "\n",
    "        for log in logs:\n",
    "            idx, state, timestamp = log.split(':')\n",
    "            idx = int(idx)\n",
    "            timestamp = int(timestamp)\n",
    "            if state == 'start':\n",
    "                if stack:\n",
    "                    res[stack[-1][0]] += timestamp - stack[-1][1]\n",
    "                    #stack[-1][1] = timestamp\n",
    "                stack.append([idx, timestamp])\n",
    "            else:\n",
    "                top_log = stack.pop()\n",
    "                res[idx] += timestamp - top_log[1] + 1\n",
    "                if stack:\n",
    "                    stack[-1][1] = timestamp + 1 \n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "\n",
    "        ans = [0] * n\n",
    "        id_stack = []\n",
    "        time_stack = []\n",
    "        res = 0\n",
    "\n",
    "        for log in logs:\n",
    "            fid, status, timestamp = log.split(\":\")\n",
    "            fid, timestamp = int(fid), int(timestamp)\n",
    "            if status == \"start\":\n",
    "                id_stack.append(fid)\n",
    "                time_stack.append(timestamp - res)\n",
    "            else:\n",
    "                time = timestamp - time_stack.pop() - res + 1\n",
    "                ans[fid] += time\n",
    "                res += time\n",
    "                id_stack.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        logs.sort(key= lambda x: x[-1])\n",
    "        log_tuples = [(int(log.split(\":\")[0]), log.split(\":\")[1], int(log.split(\":\")[2])) for log in logs]\n",
    "        log_tuples.sort(key=lambda x: x[2])\n",
    "\n",
    "        ans = [0] * n\n",
    "        id_stack = []\n",
    "        time_stack = []\n",
    "        res = 0\n",
    "\n",
    "        for (fid, status, timestamp) in log_tuples:\n",
    "            if status == \"start\":\n",
    "                id_stack.append(fid)\n",
    "                time_stack.append(timestamp - res)\n",
    "            else:\n",
    "                time = timestamp - time_stack.pop() - res + 1\n",
    "                ans[fid] += time\n",
    "                res += time\n",
    "                id_stack.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "\n",
    "        res = [0] * n\n",
    "        stack = []\n",
    "\n",
    "        for log in logs:\n",
    "            (func, operation, timestamp) = log.split(\":\")\n",
    "\n",
    "            function, time = int(func), int(timestamp)\n",
    "\n",
    "            if operation == \"start\":\n",
    "                if stack:\n",
    "                    res[stack[-1][0]] += time - stack[-1][1]\n",
    "                    stack[-1][1] = timestamp\n",
    "\n",
    "                stack.append([function, time])\n",
    "            \n",
    "            else:\n",
    "                f, t = stack.pop()\n",
    "\n",
    "                res[f] += time - t + 1\n",
    "\n",
    "                if stack:                      # still function in call stack\n",
    "                    stack[-1][1] = time + 1       # notice this, need to plus 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "        pre_start = 0\n",
    "        for log in logs:\n",
    "            f_id, flag, time = log.split(\":\")\n",
    "            f_id, time = int(f_id), int(time)\n",
    "            if flag == \"start\":\n",
    "                if stack:\n",
    "                    res[stack[-1]] += time - pre_start\n",
    "                stack.append(f_id)\n",
    "                pre_start = time\n",
    "            else:\n",
    "                res[stack.pop()] += time - pre_start + 1 # +=\n",
    "                pre_start = time + 1\n",
    "        return res\n",
    "\n",
    "# 很明显此题应该用到栈。遇到start就入栈，遇到end就出栈。\n",
    "\n",
    "# stack<pair<int,int>>Stack; //记录id和时刻\n",
    "# 遇到end（该事件的结束点）时，出栈一个元素（该事件的起始点）做匹配，算出这个事件A的时间差，累计在这个事件A上（用一个数组来记录）。同时，因为这个事件A占用的时间要从它的上级事件中扣除，所以还要考察此时的栈顶元素B，在相应B的runtime记录里减去这段时间。这种补偿只需要做一次，因为等事件B退栈时，所占用的总时间（包括A的）也会再从更上级事件C里面扣除的。以此类推。\n",
    "\n",
    "# 注意start和end的计时标准不一致。比较巧妙的方法就是对于end所标记的时刻，人为加上1，这样计算时间差的时候就可以直接相减。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        st = []\n",
    "        ans = [0] * n\n",
    "        for log in logs:\n",
    "            idx, tp, time = log.split(':')\n",
    "            idx, time = int(idx), int(time)\n",
    "            if tp[0] == 's':\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += time - st[-1][1]\n",
    "                    st[-1][1] = time\n",
    "                st.append([idx, time])\n",
    "            else:\n",
    "                i, t = st.pop()\n",
    "                ans[idx] += time - t + 1\n",
    "                if st:\n",
    "                    st[-1][1] = time + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        # stack = []\n",
    "        # prev_time = 0 \n",
    "        # cum_time = [0] * n #累计每个funcid的时间\n",
    "\n",
    "\n",
    "        # for log in logs:\n",
    "        #     func_id,call_type, timestamp = log.split(':')\n",
    "        #     func_id = int(func_id)\n",
    "        #     timestamp = int(timestamp)\n",
    "\n",
    "        #     if call_type == 'start':\n",
    "\n",
    "        #         if stack:\n",
    "        #             cum_time[stack[-1]] += timestamp - prev_time\n",
    "\n",
    "        #         stack.append(func_id) #存func id\n",
    "        #         prev_time = timestamp\n",
    "            \n",
    "        #     else:\n",
    "\n",
    "        #         cum_time[stack.pop()] += timestamp - prev_time +1\n",
    "        #         prev_time = timestamp + 1\n",
    "        \n",
    "        # return cum_time\n",
    "\n",
    "\n",
    "        execution_time = [0]*n\n",
    "        func_stack = []\n",
    "        prev_time = 0\n",
    "\n",
    "        for log in logs:\n",
    "            func_id, call_type,timestamp = log.split(':')\n",
    "            func_id = int(func_id)\n",
    "            timestamp = int(timestamp)\n",
    "\n",
    "            if call_type == 'start':\n",
    "                if func_stack:\n",
    "                    execution_time[func_stack[-1]] += timestamp -prev_time\n",
    "                \n",
    "                func_stack.append(func_id)\n",
    "                prev_time = timestamp\n",
    "\n",
    "\n",
    "\n",
    "            else:\n",
    "                execution_time[func_stack.pop()] += timestamp - prev_time +1\n",
    "                prev_time = timestamp +1 \n",
    "        return execution_time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        result, stack, prev_timestamp = [0] * n, [], 0\n",
    "        for i, log in enumerate(logs):\n",
    "            log_data = log.split(\":\")\n",
    "            fid, is_start, timestamp = int(log_data[0]), log_data[1] == \"start\", int(log_data[2])\n",
    "            if is_start:\n",
    "                if stack:\n",
    "                    stack[-1][1] += timestamp - prev_timestamp\n",
    "                stack.append([fid, 0])\n",
    "                prev_timestamp = timestamp\n",
    "            else:\n",
    "                stack[-1][1] += timestamp - prev_timestamp + 1\n",
    "                poped_fid, poped_duration = stack.pop()\n",
    "                result[poped_fid] += poped_duration\n",
    "                prev_timestamp = timestamp + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(':')\n",
    "            idx, timestamp = int(idx), int(timestamp)\n",
    "            if tp[0] == 's':\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += timestamp - st[-1][1]\n",
    "                    st[-1][1] = timestamp\n",
    "                st.append([idx, timestamp])\n",
    "            else:\n",
    "                i, t = st.pop()\n",
    "                ans[i] += timestamp - t + 1\n",
    "                if st:\n",
    "                    st[-1][1] = timestamp + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        def helper(log):\n",
    "            idx, mark, time = log.split(\":\")\n",
    "            return int(idx), mark == \"start\", int(time)\n",
    "\n",
    "        stack, ans, total = [], [0] * n, 0\n",
    "        for lg in logs:\n",
    "            idx, is_start, time = helper(lg)\n",
    "            if is_start:\n",
    "                stack.append(time - total)\n",
    "            else:\n",
    "                d = stack.pop()\n",
    "                diff = time + 1 - d - total\n",
    "                ans[idx] += diff\n",
    "                total += diff\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        duration = [0 for _ in range(n)]\n",
    "        hislen = len(logs)\n",
    "        stackid = []\n",
    "        stackt = []\n",
    "        for i in range(hislen):\n",
    "            log = logs[i].split(':')\n",
    "            if log[1]=='start':\n",
    "                stackid.append(int(log[0]))\n",
    "                stackt.append(int(log[2]))\n",
    "                continue\n",
    "            id0 = int(log[0])\n",
    "            t0 = int(log[2])\n",
    "            aid = stackid.pop()\n",
    "            at = stackt.pop()\n",
    "            duration[aid] += t0-at+1\n",
    "            if len(stackt)>0:\n",
    "                stackt = [i+t0-at+1 for i in stackt]\n",
    "        return duration\n",
    "\n",
    " \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans = [0]*n\n",
    "        stack = []\n",
    "        spend = []\n",
    "        for log in logs:\n",
    "            info = log.split(\":\")\n",
    "            if info[1] == \"end\":\n",
    "                func, _,start_time =  stack.pop()\n",
    "                start_time = int(start_time)\n",
    "                res = int(info[2]) - start_time+1\n",
    "                # print(spend)\n",
    "                index =len(spend)-1\n",
    "                while index>=0  and spend[index][0]>start_time:\n",
    "                    res -= spend[index][1]\n",
    "                    index-=1\n",
    "                spend.append((start_time,res ))\n",
    "                ans[int(func)] += res\n",
    "            else:\n",
    "                stack.append(info)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        last_end = -1\n",
    "        last_start = -1\n",
    "        statics = {}\n",
    "        for i in range(len(logs)):\n",
    "            exp = logs[i].split(':')\n",
    "            event = int(exp[0])\n",
    "            action = exp[1]\n",
    "            timestamp = int(exp[2])\n",
    "\n",
    "            if len(stack) > 0:\n",
    "                last_log = logs[i-1]\n",
    "                last_log = last_log.split(':')\n",
    "                last_status = last_log[1]\n",
    "                if last_status == 'end' and action == 'start':\n",
    "                    if timestamp > 1 + last_end:\n",
    "                        lasting_event = stack[-1]\n",
    "                        last_event = lasting_event[0]\n",
    "                        if last_event not in statics.keys():\n",
    "                            statics[last_event] = 0\n",
    "                        statics[last_event] += (timestamp - last_end - 1)\n",
    "\n",
    "            if action == 'start':\n",
    "                tmp_list = [event,timestamp,-1]\n",
    "                if len(stack) > 0 and stack[-1][2] == -1:\n",
    "                    stack[-1][2] = timestamp\n",
    "                stack.append(tmp_list)\n",
    "            elif action == 'end':\n",
    "                event_action_tmp = stack.pop()\n",
    "                start_tmp = event_action_tmp[1]\n",
    "                if last_start < start_tmp:\n",
    "                    time_tmp = timestamp - start_tmp + 1\n",
    "                else:\n",
    "                    time_tmp = timestamp - last_end + event_action_tmp[2] - start_tmp\n",
    "                if event not in statics.keys():\n",
    "                    statics[event] = 0\n",
    "                statics[event] += time_tmp\n",
    "                last_start = start_tmp\n",
    "                last_end = timestamp\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(statics[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(':')\n",
    "            idx, timestamp = int(idx), int(timestamp)\n",
    "            if tp[0] == 's':\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += timestamp - st[-1][1]\n",
    "                    st[-1][1] = timestamp\n",
    "                st.append([idx, timestamp])\n",
    "            else:\n",
    "                i, t = st.pop()\n",
    "                ans[i] += timestamp - t + 1\n",
    "                if st:\n",
    "                    st[-1][1] = timestamp + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        '''\n",
    "        重复时间\n",
    "        - 1. 当logs[i]为函数调用 从该函数的调用时间到上一次记录的当前时间，这段是前一函数的执行时间 ts - cur\n",
    "            即若栈不为空，则将该时间累加到栈顶对应的函数上，然后将Log[i]入栈，同时更新当前时间\n",
    "        - 2. 为函数结束：此时栈顶元素必然是该函数的调用记录，此时 log[i]的结束时间与上一次记录的当前时间的时长 ts - cur + 1，必然是该函数的执行时间，将其累加到当前函数中，并更新当前时间\n",
    "        '''\n",
    "        # logs.sort(key=lambda x: int(x.split(':')[-1]))  # 非必要操作\n",
    "        ans = [0] * n\n",
    "        st = list()\n",
    "        for log in logs:\n",
    "            function_id, tag, timestamp = log.split(':')\n",
    "            function_id, timestamp = map(int, (function_id, timestamp))\n",
    "            if tag == \"start\":\n",
    "                if st:\n",
    "                    cur_id = st[-1]\n",
    "                    ans[cur_id] += timestamp - cur\n",
    "                st.append(function_id)\n",
    "                cur = timestamp\n",
    "            else:\n",
    "                st.pop()\n",
    "                ans[function_id] += timestamp - cur + 1\n",
    "                cur = timestamp + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(':')\n",
    "            idx, timestamp = int(idx), int(timestamp)\n",
    "            if tp[0] == 's':\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += timestamp - st[-1][1]\n",
    "                    st[-1][1] = timestamp\n",
    "                st.append([idx, timestamp])\n",
    "            else:\n",
    "                i, t = st.pop()\n",
    "                ans[i] += timestamp - t + 1\n",
    "                if st:\n",
    "                    st[-1][1] = timestamp + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        #https://www.youtube.com/watch?v=CBJI_lZxYU8&ab_channel=CrackingFAANG\n",
    "        #  n = 2, logs = [\"0:start:0\",\"1:start:2\",\"1:end:5\",\"0:end:6\"]\n",
    "        #注意这题 func0 start at 0 ,因为单线程，func2 start at 2 的时候，func0运行了2秒\n",
    "        #但是func1 end at 5指的是在5分钟的最后，也就是第6分开始的时候end的。然后func0 end 6其实是运行了6-7一整秒\n",
    "        # 此处因为单线程，所以同时只能运行一个程序。用了stack的概念，如果start 我们就push to stack, 如果end，我们pop the stack，计算delta\n",
    "        # 注意end at 5,是end inclusive,其实是6的开头end的， 要+1\n",
    "\n",
    "\n",
    "#         在Python中，当我们使用列表作为栈时：\n",
    "\n",
    "# “栈顶”是列表的最后一个元素。\n",
    "# “栈底”是列表的第一个元素。\n",
    "# 因此，当我们说“堆顶元素”或“栈顶元素”时，我们指的是列表的最后一个元素。我们使用 list[-1] 来访问它，\n",
    "# 使用 list.append(item) 来将一个元素推入栈顶，使用 list.pop() 来从栈顶弹出一个元素。\n",
    "\n",
    "        #注意top of the stack就是currently running的func\n",
    "        # 用array store result\n",
    "        execution_times = [0]*n #保存每个func最终的累计运行时间 ,list（其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。）\n",
    "        call_stack = [] #也用list，用来存储运行的func的id（也是index）\n",
    "        prev_start_time = 0 #初始化每个func的前一个开始的时间，用于计算时间差\n",
    "\n",
    "        for log in logs:\n",
    "            #先parse出来信息\n",
    "            func_id, call_type, timestamp = log.split(':')\n",
    "            func_id = int(func_id) #convert to int \n",
    "            timestamp = int(timestamp) #convert to int \n",
    "            \n",
    "            if call_type == 'start': #如果是start，我们就加入stack\n",
    "                if call_stack: # 但如果之前stack里有东西，说明之前有个func还在运行，要停止但不用删除因为他还没end，因为单线程。只需count上一个func运行的时间\n",
    "                    # call_stack[-1] 是index，第一次循环代表index0 \n",
    "                    # 这只是访问栈顶的元素，不会从栈中删除它。\n",
    "                    # 它等效于查看栈顶的元素（正在运行的），但不移除它。\n",
    "                    # 如果栈是空的，这会引发一个错误 #stack[-1]就是堆顶的那个\n",
    "                    execution_times[call_stack[-1]] += timestamp -prev_start_time #prev_start_time是上个函数开始的时间\n",
    "                \n",
    "                call_stack.append(func_id) #现在的func id 加入stack,这个id刚好是从0开始的，可以当index用\n",
    "                prev_start_time = timestamp #新func的新的start time更新\n",
    "            else: #如果是end\n",
    "                #call_stack.pop()删除call_stack中堆顶，因为end了），同时返回index，刚好对应上excu里面目前end 的func的位置，更新他的时间\n",
    "                # call_stack.pop():\n",
    "                # 这会移除并返回栈顶的元素。\n",
    "                # 这是一个修改栈的操作，因为它实际上从栈中删除了一个元素。\n",
    "                # 如果栈是空的，这也会引发一个错误\n",
    "                execution_times[call_stack.pop()] += timestamp - prev_start_time+1 #注意end at 5,是end inclusive,其实是6的开头end的， 要+1\n",
    "                \n",
    "                prev_start_time = timestamp + 1 #此func结束了，下一个func要继续了，那就更新下一个函数运行开始的时间，注意是end at 6,所以还是5+1\n",
    "        return execution_times\n",
    "\n",
    "# O（N\n",
    "# O(N)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        #https://www.youtube.com/watch?v=CBJI_lZxYU8&ab_channel=CrackingFAANG\n",
    "        execution_times = [0]*n \n",
    "        call_stack = []\n",
    "        prev_start_time = 0\n",
    "\n",
    "        for log in logs:\n",
    "            func_id, call_type, timestamp = log.split(':')\n",
    "            func_id = int(func_id)\n",
    "            timestamp = int(timestamp)\n",
    "            \n",
    "            if call_type == 'start':\n",
    "                if call_stack:\n",
    "                    execution_times[call_stack[-1]] += timestamp -prev_start_time\n",
    "                \n",
    "                call_stack.append(func_id)\n",
    "                prev_start_time = timestamp\n",
    "            else: \n",
    "                execution_times[call_stack.pop()] += timestamp - prev_start_time+1 \n",
    "                prev_start_time = timestamp + 1\n",
    "        return execution_times\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(':')\n",
    "            idx, timestamp = int(idx), int(timestamp)\n",
    "            if tp[0] == 's':\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += timestamp - st[-1][1]\n",
    "                    st[-1][1] = timestamp\n",
    "                st.append([idx, timestamp])\n",
    "            else:\n",
    "                i, t = st.pop()\n",
    "                ans[i] += timestamp - t + 1\n",
    "                if st:\n",
    "                    st[-1][1] = timestamp + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        funcTimes = [0] * n\n",
    "        callStack = []\n",
    "        \n",
    "        def parse(log):\n",
    "            items = log.split(':')\n",
    "            funcId = int(items[0])\n",
    "            op = items[1]\n",
    "            curTime = int(items[2])\n",
    "            return funcId, op, curTime\n",
    "\n",
    "        for log in logs:\n",
    "            funcId, op, curTime = parse(log)\n",
    "            if op == 'end':\n",
    "                funcId, prevTime, repTime = callStack.pop()\n",
    "                computeTime = curTime - prevTime + 1 - repTime\n",
    "                funcTimes[funcId] += computeTime\n",
    "                if callStack:\n",
    "                    callStack[-1][2] += curTime - prevTime + 1\n",
    "            else:\n",
    "                callStack.append([funcId, curTime, 0])\n",
    "        \n",
    "        return funcTimes\n",
    "\n",
    "'''\n",
    "\n",
    "prevTime = 0\n",
    "stack = [0]\n",
    "\n",
    "curTime = 2\n",
    "computeTime = curTime - preV\n",
    "stack = [0, 1]\n",
    "add cur - prevCur to \n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parse_log(self, log):\n",
    "        log_parts = log.split(':')\n",
    "        func_id = int(log_parts[0])\n",
    "        mode = log_parts[1]\n",
    "        time = int(log_parts[2])\n",
    "        return func_id, mode, time\n",
    "\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        func_intervals = [0] * n\n",
    "        stk = collections.deque([])\n",
    "        child_time = 0\n",
    "        for log in logs:\n",
    "            func_id, mode, time = self.parse_log(log)\n",
    "            if mode == \"start\":\n",
    "                stk.append((\"start\", func_id, time))\n",
    "            else:\n",
    "                # mode = end\n",
    "                _, _, prev_time = stk.pop()\n",
    "                func_intervals[func_id] += (time - prev_time + 1)\n",
    "\n",
    "                if stk:\n",
    "                    prev_func_id = stk[-1][1]\n",
    "                    func_intervals[prev_func_id] -= (time - prev_time + 1)\n",
    "                    \n",
    "        return func_intervals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\r\n",
    "        ans = [0]*n\r\n",
    "        stack = []\r\n",
    "        for log in logs:\r\n",
    "            function_id,tp,timestamp = log.split(':')\r\n",
    "            function_id,timestamp = int(function_id),int(timestamp)\r\n",
    "            if tp == 'start':\r\n",
    "                if stack:\r\n",
    "                    ans[stack[-1][0]] += timestamp - stack[-1][1]\r\n",
    "                stack.append([function_id,timestamp])\r\n",
    "            else:\r\n",
    "                i,t=stack.pop()\r\n",
    "                ans[i]+=timestamp - t + 1\r\n",
    "                if stack:\r\n",
    "                    stack[-1][1] = timestamp + 1\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        # time = [0] * n\n",
    "        # function_stk = []\n",
    "        # pre_time = []\n",
    "        # for l in logs:\n",
    "        #     f, mode, t = l.split(':')\n",
    "        #     if mode == 'start':\n",
    "        #         function_stk.append((f, t))\n",
    "        #         pre_time.append(0)\n",
    "        #     else:\n",
    "        #         cur_time = int(t) - int(function_stk[-1][1]) + 1 - pre_time[-1]\n",
    "        #         time[int(f)] += cur_time\n",
    "        #         pre_time[-1] += cur_time\n",
    "        #         function_stk.pop()\n",
    "        #         if function_stk:\n",
    "        #             p = pre_time.pop()\n",
    "        #             pre_time[-1] += p\n",
    "        #         else:\n",
    "        #             pre_time = []\n",
    "        # return time\n",
    "\n",
    "        # ----------------------------\n",
    "        def parse_log(log):\n",
    "            idx, mode, time = log.split(':')\n",
    "            return int(idx), mode == 'start', int(time)\n",
    "        \n",
    "        stk, res, total = [], [0]*n, 0\n",
    "        for l in logs:\n",
    "            idx, is_start, time = parse_log(l)\n",
    "            if is_start:\n",
    "                stk.append((idx, time, total))\n",
    "            else:\n",
    "                i, t, pre = stk.pop()\n",
    "                cur_time = time - t + 1 - total + pre\n",
    "                res[i] += cur_time\n",
    "                total += cur_time\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\r\n",
    "        res = [0] * n\r\n",
    "        st = []\r\n",
    "        for log in logs:\r\n",
    "            idx, op, time = log.split(':')\r\n",
    "            idx, time = int(idx), int(time)\r\n",
    "            if op[0] is 's':\r\n",
    "                if st:\r\n",
    "                    res[st[-1][0]] += time - st[-1][1]\r\n",
    "                    st[-1][1] = time\r\n",
    "                st.append([idx, time])\r\n",
    "            else:\r\n",
    "                i, t = st.pop()\r\n",
    "                res[i] += time - t + 1\r\n",
    "                if st:\r\n",
    "                    st[-1][1] = time + 1\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:\r\n",
    "        ans = [0] * n\r\n",
    "        stack = []\r\n",
    "        for l in logs:\r\n",
    "            id, op, time = l.split(':')\r\n",
    "            id = int(id)\r\n",
    "            time = int(time)\r\n",
    "            if op == 'start':\r\n",
    "                if stack:\r\n",
    "                    ans[stack[-1][0]] += time - stack[-1][1]\r\n",
    "                stack.append((id, time))\r\n",
    "            else:\r\n",
    "                ans[stack[-1][0]] += time - stack[-1][1] + 1\r\n",
    "                stack.pop()\r\n",
    "                if stack:\r\n",
    "                    stack[-1] = (stack[-1][0], time + 1)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        a = [0] * n\n",
    "        b = []\n",
    "        t = 0\n",
    "        for i in logs:\n",
    "            l = i.split(\":\")\n",
    "            x = int(l[0])\n",
    "            y = int(l[2])\n",
    "            if l[1] == \"end\":\n",
    "                a[b[-1]] += y - t + 1\n",
    "                t = y + 1\n",
    "                b.pop(-1)\n",
    "            else:\n",
    "                if b != []:\n",
    "                    a[b[-1]] += y - t \n",
    "                b.append(x)\n",
    "                t = y\n",
    "            #print(a)\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\r\n",
    "        # if n==1:\r\n",
    "        #     return int(logs[-1].split(':')[-1])+1\r\n",
    "        ret=[0]*n\r\n",
    "        tid_stack=[]\r\n",
    "        pre_time=0\r\n",
    "        for log in logs:\r\n",
    "            parts=log.split(':')\r\n",
    "            tid=int(parts[0])\r\n",
    "            flag=parts[1][0]\r\n",
    "            time=int(parts[2])\r\n",
    "            if flag=='e':\r\n",
    "                pre_id=tid_stack.pop()\r\n",
    "                ret[pre_id]+=time-pre_time+1\r\n",
    "                pre_time=time+1\r\n",
    "            else:\r\n",
    "                if tid_stack:\r\n",
    "                    pre_id=tid_stack[-1]\r\n",
    "                    ret[pre_id]+=time-pre_time\r\n",
    "                tid_stack.append(tid)\r\n",
    "                pre_time=time\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        times = {}\n",
    "        for i in range(n):\n",
    "            times[i] = 0\n",
    "        times[-1] = 0\n",
    "        last = [-1]\n",
    "        lasttime = 0\n",
    "        for log in logs:\n",
    "            logid, logmark, logtime = log.split(\":\")\n",
    "            logtime = int(logtime)\n",
    "            logid = int(logid)\n",
    "            lastid = last[-1]\n",
    "            if logmark == \"end\":\n",
    "                times[lastid] += logtime - lasttime + 1\n",
    "                last.pop()\n",
    "                lasttime = logtime + 1\n",
    "            else:\n",
    "                times[lastid] += logtime - lasttime\n",
    "                last.append(logid)\n",
    "                lasttime = logtime\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(times[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "\n",
    "\n",
    "        \n",
    "        times = [0]*n \n",
    "\n",
    "\n",
    "        cur_time = 0\n",
    "\n",
    "        stack = []\n",
    "        m =len(logs)\n",
    "\n",
    "        ans = [0]*n\n",
    "        for i in range(m):\n",
    "            log =logs[i].split(\":\")\n",
    "\n",
    "            id_cpu = int(log[0])\n",
    "            state = log[1]\n",
    "            time_x = int(log[2])\n",
    "            if stack:\n",
    "                pre_id,pre_state, pre_time = stack[-1]\n",
    "                if state==\"start\":\n",
    "                    ans[pre_id] += time_x-cur_time\n",
    "                    stack.append((id_cpu,state, time_x))\n",
    "                    cur_time = time_x \n",
    "                elif state==\"end\":\n",
    "                    ans[id_cpu] += time_x-cur_time+1\n",
    "                    cur_time = time_x+1 \n",
    "                    stack.pop()\n",
    "\n",
    "            elif not stack:\n",
    "                cur_time = time_x \n",
    "                stack.append((id_cpu,state, time_x))\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(':')\n",
    "            idx, timestamp = int(idx), int(timestamp)\n",
    "\n",
    "            if tp == 'start':\n",
    "                if stack:\n",
    "                    res[stack[-1][0]] += timestamp - stack[-1][1]\n",
    "                    stack[-1][1] = None\n",
    "                stack.append([idx, timestamp])\n",
    "            elif tp == 'end':\n",
    "                prev_idx, prev_timestamp = stack.pop()\n",
    "                res[prev_idx] += timestamp - prev_timestamp + 1\n",
    "                if stack:\n",
    "                    stack[-1][1] = timestamp + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: list[str]) -> list[int]:\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(\":\")\n",
    "            idx, timestamp = int(idx), int(timestamp)\n",
    "            if tp[0] == \"s\":\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += timestamp - st[-1][1]\n",
    "                    st[-1][1] = timestamp\n",
    "                st.append([idx, timestamp])\n",
    "            else:\n",
    "                i, t = st.pop()\n",
    "                ans[i] += timestamp - t + 1\n",
    "                if st:\n",
    "                    st[-1][1] = timestamp + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        logs.sort(key= lambda x: x[-1])\n",
    "        log_tuples = [(int(log.split(\":\")[0]), log.split(\":\")[1], int(log.split(\":\")[2])) for log in logs]\n",
    "        log_tuples.sort(key=lambda x: x[2])\n",
    "\n",
    "        ans = [0] * n\n",
    "        id_stack = []\n",
    "        time_stack = []\n",
    "        res = 0\n",
    "\n",
    "        for (fid, status, timestamp) in log_tuples:\n",
    "            if status == \"start\":\n",
    "                id_stack.append(fid)\n",
    "                time_stack.append(timestamp - res)\n",
    "            else:\n",
    "                time = timestamp - time_stack.pop() - res + 1\n",
    "                ans[fid] += time\n",
    "                res += time\n",
    "                id_stack.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        queue=[]\n",
    "        # for i in qu\n",
    "        m=len(logs)\n",
    "        res=[0]*n\n",
    "        for  i in range(m):\n",
    "            fid,typ,ts=logs[i].split(\":\")\n",
    "            fid=int(fid)\n",
    "            ts=int(ts)\n",
    "            if len(queue)==0:\n",
    "                queue.append([fid,typ,ts])\n",
    "                continue\n",
    "            if typ==\"end\":\n",
    "                l_fid,l_typ,l_ts=queue.pop()\n",
    "                res[fid]+=ts-l_ts+1\n",
    "                if len(queue)>0 and  queue[-1][1]==\"hold\":\n",
    "                    l_fid,l_typ,l_ts=queue.pop()\n",
    "                    queue.append( [l_fid,\"start\",ts+1])\n",
    "               \n",
    "                     \n",
    "                \n",
    "            if typ==\"start\":\n",
    "                if len(queue)>0 and queue[-1][1]==\"start\":\n",
    "                    l_fid,l_typ,l_ts=queue.pop()\n",
    "                    res[l_fid]+=ts-1-l_ts+1\n",
    "                    queue.append( [l_fid,\"hold\",ts])\n",
    "                    queue.append( [fid,\"start\",ts])\n",
    "            # print(i,res,queue)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(':')\n",
    "            idx, timestamp = int(idx), int(timestamp)\n",
    "\n",
    "            if tp == 'start':\n",
    "                if stack:\n",
    "                    res[stack[-1][0]] += timestamp - stack[-1][1]\n",
    "                    stack[-1][1] = None\n",
    "                stack.append([idx, timestamp])\n",
    "            elif tp == 'end':\n",
    "                prev_idx, prev_timestamp = stack.pop()\n",
    "                res[prev_idx] += timestamp - prev_timestamp + 1\n",
    "                if stack:\n",
    "                    stack[-1][1] = timestamp + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ret_time = [0] * n\n",
    "        stack = []\n",
    "        active_ind = -1\n",
    "        for log in logs:\n",
    "            ind, label, time = log.split(\":\")\n",
    "            ind = int(ind)\n",
    "            time = int(time)\n",
    "            if label == 'start':\n",
    "                if active_ind >= 0:\n",
    "                    ret_time[active_ind] += time - stack[-1][1]\n",
    "                active_ind = ind\n",
    "                stack.append([active_ind, time])\n",
    "            else:\n",
    "                ret_time[active_ind] += time - stack[-1][1] + 1\n",
    "                stack.pop()\n",
    "                if(len(stack)):\n",
    "                    active_ind = stack[-1][0]\n",
    "                    stack[-1][1] = time + 1\n",
    "                else:\n",
    "                    active_ind = -1\n",
    "\n",
    "\n",
    "        return ret_time\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def exclusiveTime2(self, n: int, logs: List[str]) -> List[int]:\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for log in logs:\n",
    "            idx, tp, timestamp = log.split(':')\n",
    "            idx, timestamp = int(idx), int(timestamp)\n",
    "            if tp[0] == 's':\n",
    "                if st:\n",
    "                    ans[st[-1][0]] += timestamp - st[-1][1]\n",
    "                    st[-1][1] = timestamp\n",
    "                st.append([idx, timestamp])\n",
    "            else:\n",
    "                i, t = st.pop()\n",
    "                ans[i] += timestamp - t + 1\n",
    "                if st:\n",
    "                    st[-1][1] = timestamp + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        L = len(logs)\n",
    "        stack = []\n",
    "        ans = [0] * n\n",
    "        for log in logs:\n",
    "            (f, call, t) = log.split(\":\")\n",
    "            f, t = int(f), int(t)\n",
    "            if call == \"start\":\n",
    "                if len(stack):\n",
    "                    ff, tt = stack[-1]\n",
    "                    ans[ff] += t - tt\n",
    "                stack.append((f, t))\n",
    "            else:\n",
    "                ff, tt = stack[-1]\n",
    "                ans[f] += t - tt + 1\n",
    "                stack.pop()\n",
    "                if len(stack):\n",
    "                    (fp, tp) = stack.pop()\n",
    "                    stack.append((fp, t + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        hash_map = [0 for _ in range(n)]\n",
    "        stack = []\n",
    "        for log in logs:\n",
    "            thread_id, status, time = log.split(':')\n",
    "            if status == \"start\":\n",
    "                if stack:\n",
    "                    hash_map[stack[-1][0]] += int(time) - stack[-1][1]\n",
    "                stack.append([int(thread_id), int(time)])\n",
    "            else:\n",
    "                _, begin_time = stack.pop(-1)\n",
    "                hash_map[int(thread_id)] += int(time) - begin_time + 1\n",
    "                if stack:\n",
    "                    stack[-1][1] = int(time) + 1\n",
    "        return hash_map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:\n",
    "        pre_thr = -1\n",
    "        cur_thr = -1\n",
    "        times = [0] * n\n",
    "        stack = []\n",
    "        pre_time = 0\n",
    "        for i in range(len(logs)):\n",
    "            a = logs[i].split(':')\n",
    "            a[0],a[2] = int(a[0]),int(a[2])\n",
    "\n",
    "            #print(pre_thr,cur_thr,pre_time,a[2])\n",
    "            if a[1] == 'start':\n",
    "                stack.append([a[0],a[2]])\n",
    "                pre_thr,cur_thr = cur_thr,a[0]\n",
    "                if pre_thr != -1:\n",
    "                    times[pre_thr] += (a[2] - pre_time)\n",
    "                pre_time = a[2]\n",
    "            else:\n",
    "                a = a[2] + 1\n",
    "                times[cur_thr] += (a - pre_time)\n",
    "                pre_time = a\n",
    "                if len(stack) == 1:\n",
    "                    pre_thr,cur_thr = -1,-1\n",
    "                elif len(stack) == 2:\n",
    "                    pre_thr,cur_thr = -1,stack[-2][0]\n",
    "                else:\n",
    "                    pre_thr,cur_thr = stack[-3][0],stack[-2][0]\n",
    "                stack.pop()\n",
    "            # print(times)\n",
    "        return times\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
